package com.company.linked;

import com.company.ListNode;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * @date 2019/11/16 8:25
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        listNode.next.next.next.next = new ListNode(5);
        removeNthFromEnd(listNode,2);
    }

    // 双指针
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode left = head,right = head;
        ListNode leftPre = head;
        int le = 0;

        while (right != null) {

            if (le < n) le++;
            else {
                leftPre = left;
                left = left.next;
            }

            right = right.next;
        }

        if (left == head) return head.next;
        leftPre.next = left.next;
        return head;
    }

}
